package 第四周;

/*
 * @author  YxinMiracle
 * @date  2022-04-29 8:56
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.Arrays;

public class 矩阵中的最长递增路径 {

    int m, n;
    int[][] matrix;
    int[] dx = new int[]{0, -1, 0, 1};
    int[] dy = new int[]{-1, 0, 1, 0};
    int[][] deg;
    int ans = 0;

    public int longestIncreasingPath(int[][] matrix) {
        this.m = matrix.length;
        this.n = matrix[0].length;
        this.matrix = matrix;
        this.deg = new int[m][n]; // 全部默认为0

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, dfs(i, j)); // 深度优先搜索查询每一个点，从i，j开始走，改为记忆形递归
            }
        }
        return ans;
    }

    private int dfs(int i, int j) {
        if (deg[i][j] != 0) {
            return deg[i][j];
        }
        deg[i][j] = 1;
        for (int k = 0; k < 4; k++) {
            int nx = i + dx[k];
            int ny = j + dy[k];
            if (valid(nx, ny) && matrix[nx][ny] > matrix[i][j]) { // 表示可以继续往下走
                deg[i][j] = Math.max(deg[i][j], dfs(nx,ny) + 1);
            }
        }
        return deg[i][j];
    }


    public boolean valid(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    public static void main(String[] args) {
        int[][] deg = new int[5][5];
        for (int[] ints : deg) {
            for (int anInt : ints) {
                System.out.println(anInt);
            }
        }
        System.out.println(Arrays.toString(deg));
    }

}
